<head>
    <meta charset="UTF-8">
<title>算法提高 多米诺骨牌放置（加强版1）</title>
<link rel="stylesheet" href="../css/main.css">
</head>
 <p>&nbsp;</p>
<p>【问题描述】<br>
&nbsp;&nbsp;&nbsp;&nbsp; 有一个m 行n 列的矩形方格棋盘，用1*2 的骨牌(可横放或竖放)完全覆盖，骨牌不能重叠。但是，棋盘中有一些p个位置有破洞，坐标分别为（xi（第xi列），yi（第yi行））,这些位置不能放置骨牌了。请问有多少种不同的覆盖的方法。<br>
&nbsp;&nbsp;&nbsp;&nbsp; 请对覆盖方法总数 mod 10007 的值即可。<br>
<br>
&nbsp;<br>
<br>
【输入格式】<br>
第 1 行，三个整数数n，m，p，<br>
第 2 — p-1 行，两个整数 xi，yi 。<br>
<br>
&nbsp;<br>
<br>
【输出格式】<br>
一个整数，总数 mod 10007 的结果。<br>
<br>
&nbsp;<br>
<br>
【样例输入】<br>
2 3 2<br>
1 3<br>
2 3<br>
<br>
&nbsp;<br>
<br>
【样例输出】<br>
2<br>
<br>
&nbsp;<br>
<br>
【数据规模和约定】<br>
0&lt;n&lt;=10 , 0&lt;m&lt;=100 ，0&lt;=p&lt;=m*n。</p>